class BroadStructure {
	private BroadElement head;	
	private int breadth;
	private int depth;
	private long size;

	BroadStructure(long size, int breadth) {
		this.breadth = BroadElement.validateBreadth(breadth);
		this.size = size;
		this.depth = 1;
		
		createBroadStructure();
	}
	
	private void createBroadStructure() {
		head = new BroadElement(1, this.breadth, null, 0);
		BroadElement node = head;
		BroadElement parent = head;
		int index = 1;
		int created = 1;

		while (created < this.size) {
			//System.out.println("Before creation: insertTo="+ insertTo.toString() +", insertAt="+ insertAt);
			created++;
			node = new BroadElement(created, this.breadth, parent, index);
			parent.setRef(node, index);			
			
			index++;
			if (index > this.breadth) {
				//parent exhausted, find another one
				index = 1;
				parent = findNextParent(parent);	
				//parent.dump("createBroadStructure, created="+created+", will populate parent");
			}
		}

		sanityCheck();
	}
	
	private void sanityCheck() {
		BroadElement node;
		for(int i = 1; i <= this.breadth; i++) {
			node = head;
			int steps = 0;
			while (node.getRef(i) != null) {
				node = node.getRef(i);
				steps++;
			}
			System.out.println("Depth measured through ref number "+i+" is "+steps);
			if(steps > this.depth) {
				this.depth = steps;
			}
		}
		System.out.println("Depth is "+this.depth);
	}
	
	private BroadElement findNextParent(BroadElement parent){
		BroadElement node = parent;
		
		while (node != this.head && node.getOrder() == this.breadth) {
			//System.out.println("Entered while: insertTo="+ insertTo.toString() +", insertAt="+ insertAt);
			node = node.getParent();
		}
		
		if(node == this.head) {
			while(!node.isEmpty()) {
				node = node.getRef(1);
			}
		} else {
			node = node.getParent().getRef(node.getOrder()+1);
			while(!node.isEmpty()) {
				node = node.getRef(1);
			}
		}
		
		return node;
	}
	
	long getSize() {
		return this.size;
	}
	
	private long visited;
	long traverseDFS() {
		visited = 0;
		BroadElement node = this.head;
		while(!node.isEmpty()) {
			visited++;
			node = node.getRef(1);
		}
		
		node = node.getParent();
		while(node != null) {
			visited += node.getRefs();
			node = getNextNode(node);
		}
		
		System.out.println("Visited " + visited + " nodes");
		System.out.flush();
		return visited;
	}
	
	private BroadElement getNextNode(BroadElement node) {
		int order = node.getOrder();
		while(order == this.breadth && node != this.head) {
			node = node.getParent();
			order = node.getOrder();
		}
		if(node == this.head) {
			return null;
		}
		node = node.getParent().getRef(order+1);
		while(!node.isEmpty()) {
			visited++;
			node = node.getRef(1);
		}
		
		node = node.getParent();
		
		return node;
	}
}
